class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = S.length();
        int m = T.length();

        if (n == 0 || m == 0 || n < m) {
            return 0;
        }
        vector<vector<int> > dp(n, vector<int>(m));

        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (S[i] == T[0]) {
                ++count;
            }
            dp[i][0] = count;
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= i && j < m; ++j) {
                if (S[i] == T[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }
        return dp[n - 1][m - 1];
    }
};

